`
https://leetcode.cn/problems/rotting-oranges/
`

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function (grid) {
  const m = grid.length, n = grid[0].length
  const q = []
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      // 如果是腐烂的橘子
      if (grid[i][j] === 2) {
        // 作为腐烂起点
        q.push([i, j])
      }
    }
  }

  let time = 0
  while (q.length > 0) {
    const sz = q.length
    for (let i = 0; i < sz; i++) {
      const [x, y] = q.shift()
      for (const dir of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
        const nextX = x + dir[0]
        const nextY = y + dir[1]
        if (
          nextX >= 0 && nextX < m && nextY >= 0 && nextY < n &&
          grid[nextX][nextY] === 1
        ) {
          grid[nextX][nextY] = 2
          q.push([nextX, nextY])
        }
      }
    }
    time++
  }

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      // 如果还有新鲜的橘子，说明存在永远不会腐烂的橘子
      if (grid[i][j] === 1) {
        return -1
      }
    }
  }

  // 如果有腐烂次数，需要 -1，因为最后会多算一次
  return time === 0 ? 0 : time - 1
};